/*
二叉排序树的限定条件下的数据输出
【问题描述】

    已知二叉排序树采用二叉链表存储结构，根结点的指针为T，结点的结构为(lchild,data,rchild),其中lchild、rchild分别指向该结点左，右孩子的指针，data域存放结点数据。试编写算法，从小到大输出二叉排序树中所有数值大于等于x的结点的数据。要求先找到第一个满足条件的结点后，再依次输出其他满足条件的结点。

【输入形式】

    多组数据，每组二行。第一行为空格分隔的多个数字，最后以0表示输入结束，对应二叉排序树中的n个结点。第二行为一个数字x。

【输出格式】

     每组数据输出一行。从小到大输出大于等于x的结点数据。每个数据用空格分隔。
*/

#include <iostream>
#include <stack>
#include <queue>
using namespace std;
typedef struct BSTNode{
    int data;
    struct BSTNode *lchild, *rchild;
}BSTNode, *BSTree;

void InsertBST(BSTree &T, int x)//插入二叉排序树
{
    if(!T)//空树
    {
        BSTree p;
        p = new BSTNode;//新二叉排序树结点
        p->data = x;
        p->lchild = p->rchild = NULL;
        T = p;
    }
    else if(x < T->data)
        InsertBST(T->lchild, x);//小的为左孩子
    else if(x > T->data)
        InsertBST(T->rchild, x);//大的为右孩子
}

void CreateBST(BSTree &T)//建立二叉排序树
{
    T = NULL;
    int x;
    cin>>x;
    while(x != 0)
    {
        InsertBST(T, x);
        cin>>x;
    }
}

void ldroutput(BSTree T,int x)//中序遍历二叉排序树为从小到大顺序
{//从小到大输出二叉排序树中所有数值大于等于x的结点的数据
    if(T)
    {
        ldroutput(T->lchild,x);
        if(T->data>=x)
            cout << T->data << " ";
        ldroutput(T->rchild,x);
    }
}

int depth(BSTree T)//二叉树深度
{
    int m = 0, n = 0;
    if(T==NULL)//空树
        return 0;
    else
    {
        m=depth(T->lchild);//左孩子深度
        n=depth(T->rchild);//右孩子深度
        if(m>n)
            return m + 1;
        else
            return n + 1;
    }
}

int anvtree(BSTree T)
{
    if(T==NULL)//空树平衡
        return 1;
    int l, r;
    l = depth(T->lchild);
    r = depth(T->rchild);
    if((l-r)>1||(l-r)<-1)//不平衡
        return 0;
    return anvtree(T->lchild) && anvtree(T->rchild);
}

int main()
{
    BSTree T;
    CreateBST(T);//创建二叉排序树
    if(anvtree(T))
        cout << "true";
    else
        cout << "false";
    return 0;
}